package com.algorithm.learning.base.链表;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: algorithm-learning
 * @description: 可以利用优先级队列
 * @author: YuKai Fan
 * @create: 2024/8/24 17:28
 **/
public class 合并K个有序链表 {

    public static class ListNode {
        private ListNode next;
        private int val;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }

    /**
     * 首先题目给的是一个数组，数组中都是一个ListNode链表的头节点，例如：
     *      * [ListNode(1), ListNode(4), ListNode(2)]
     *      * 其中每个ListNode都是一个有序链表，
     *          ListNode(1) -> ListNode(2) -> ListNode(3)
     *          ListNode(4) -> ListNode(6) -> ListNode(7)
     *          ListNode(2) -> ListNode(5) -> ListNode(6)
     *      * 要求将这些有序链表合成一个有序链表，
     *          ListNode(1) -> ListNode(2) -> ListNode(2) -> ListNode(3) -> ListNode(4) -> ListNode(5) -> ListNode(6) -> ListNode(6) -> ListNode(7)
     *
     * 思路：可以利用优先级队列的自动排序实现。
     *
     * 1、 优先级队列是天然有序的，即每次入队，都会先排序；
     * 2、 我们首先可以将每个数组中的元素，放入队列中，再弹出第一个，那么弹出的元素就是最小的，
     * 3、 然后再将弹出ListNode的next节点入队，如此反复，直到next节点为null
     *
     *
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        if (lists.length == 1) {
            return lists[0];
        }
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(new ListNodeComparator());
        // 先将整个数组的元素入队，而数组的元素就是各个链表的头节点
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                priorityQueue.add(lists[i]);
            }
        }
        ListNode head = priorityQueue.poll();
        ListNode tmp = head;
        while (!priorityQueue.isEmpty()) {
            ListNode cur = priorityQueue.poll();
            head.next = cur;
            head = cur;

            if (cur.next != null) {
                priorityQueue.add(cur.next);
            }
        }
        return tmp;
    }

    public static void main(String[] args) {
        ListNode ListNode = new ListNode(1);
        ListNode.next = new ListNode(2);
        ListNode.next.next = new ListNode(3);

        ListNode ListNode1 = new ListNode(4);
        ListNode1.next = new ListNode(6);
        ListNode1.next.next = new ListNode(7);

        ListNode ListNode2 = new ListNode(2);
        ListNode2.next = new ListNode(5);
        ListNode2.next.next = new ListNode(6);

        ListNode[] ListNodes = new ListNode[] {ListNode, ListNode1, ListNode2};

        ListNode ListNode3 = mergeKLists(ListNodes);
        while (ListNode3 != null) {
            System.out.println(ListNode3.val);
            ListNode3 = ListNode3.next;
        }
    }
}
